from functools import lru_cache
import time

def calcTime(func):
        '''
        函数修饰器, 用来计算各个排序算法的执行时间
        最终返回一个 list [temp, time_sum]
        '''
        def warpper (*args, **kwds):
            time_start = time.perf_counter()
            temp = func(*args, **kwds)
            time_end = time.perf_counter()
            time_sum = time_end - time_start
            return [temp, time_sum*1000]
        return warpper

class Solution:
    @calcTime
    def wordBreak(s: str, wordDict: list) -> list:
        @lru_cache(None)
        def backtrack(index: int) -> list:
            if index == len(s):
                return [[]]
            ans = list()
            for i in range(index + 1, len(s) + 1):
                word = s[index:i]
                if word in wordSet:
                    nextWordBreaks = backtrack(i)
                    for nextWordBreak in nextWordBreaks:
                        ans.append(nextWordBreak.copy() + [word])
            return ans
        
        wordSet = set(wordDict)
        breakList = backtrack(0)
        return [" ".join(words[::-1]) for words in breakList]


if __name__ == '__main__':
    s = "catsanddog"
    wordDict = ["cat","cats","and","sand","dog"]

    print(Solution.wordBreak(s, wordDict))